let quick = [];

for (let index = 0; index < 8; index++) {
  quick.push(Math.round(Math.random()*20 + 1));
}
console.log(quick);
quickFn(quick, 0, quick.length - 1);
console.log(quick);

function quickFn(arr, left, right){
  if(left >= right){
    return; //递归出口
  }
  let pivot = findPivot(arr, left, right);  // 获取主元
  let l = left;
  let r = right - 1;  //主元前一位
  
  while(l < r){
    // 左边开始比较，直到有比主元大的
    while(arr[l] < pivot){
      l++;
    }
    // 右边开始比较，直到有比主元小的
    while(arr[r] > pivot){
      r--;
    }
    // 交换
    if(l < r){
      trans(arr, l, r);
    }
  }
  // 主元换位
  trans(arr, l, right);
  quickFn(arr, left, l - 1);
  quickFn(arr, r + 1, right)
}

function findPivot(arr, left, right){
  let center = Math.floor((left + right) / 2);
  arr[left] > arr[center]? trans(arr, left, center): 1;
  arr[left] > arr[right]? trans(arr, left, right) : 1;
  arr[center] < arr[right]? 1 : trans(arr, center, right);
  // 将主元放到最后
  trans(arr, center, right);
  return arr[right];  //返回主元
}

function trans(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}